package com.wc.算法提高课.B第二章_搜索.DFS之剪枝与优化.数独;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/9/28 23:45
 * @description https://www.acwing.com/problem/content/168/
 */
public class Main {
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 9, M = 1 << N;
    // ones[state] 表示state中有几个1， map[1 << i] = i, 表示第i位为1
    static int[] ones = new int[M], map = new int[M];
    static int[] row = new int[N], col = new int[N];
    static int[][] cell = new int[3][3];
    static char[] str;

    public static void main(String[] args) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                ones[i] += i >> j & 1;
            }
        }
        for (int i = 0; i < N; i++) map[1 << i] = i;
        while (true) {
            str = sc.next().toCharArray();
            if (str[0] == 'e') break;
            init();
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (str[i * N + j] != '.') {
                        int v = str[i * N + j] - '1';
                        draw(i, j, v, true);
                    } else cnt++;
                }
            }
            dfs(cnt);
            out.println(new String(str));
        }

        out.flush();
    }

    static boolean dfs(int cnt) {
        if (cnt == 0) return true;
        int minv = 10;
        int x, y;
        x = y = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (str[i * N + j] == '.') {
                    int state = get(i, j);
                    if (ones[state] < minv) {
                        minv = ones[state];
                        x = i;
                        y = j;
                    }
                }
            }
        }
        for (int i = get(x, y); i > 0; i -= lowbit(i)) {
            int t = map[lowbit(i)];
            draw(x, y, t, true);
            if (dfs(cnt - 1)) return true;
            draw(x, y, t, false);
        }

        return false;
    }

    static int lowbit(int x) {
        return x & -x;
    }

    static int get(int x, int y) {
        return row[x] & col[y] & cell[x / 3][y / 3];
    }

    static void init() {
        for (int i = 0; i < N; i++) row[i] = col[i] = M - 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cell[i][j] = M - 1;
            }
        }

    }

    static void draw(int x, int y, int t, boolean isDraw) {
        if (isDraw) {
            str[x * N + y] = (char) (t + '1');
        } else str[x * N + y] = '.';
        int v = 1 << t;
        if (!isDraw) v = -v;
        row[x] -= v;
        col[y] -= v;
        cell[x / 3][y / 3] -= v;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
